package difficulty;

import java.util.ArrayList;
import java.util.List;

public class L51 {
    public List<List<String>> solveNQueens(int n) {
        //dfs+位运算
        //时间复杂度O(n^3)
        List<List<String>> res = new ArrayList<>();
        solveNQueens(res,new ArrayList<>(),n,0,0,0);
        return res;
    }

    public void solveNQueens(List<List<String>> res,List<String> list,int n, int column, int pie,int na) {
        if (n == list.size()) {
            res.add(new ArrayList<>(list));
            return;
        }
        int bit = (~(column | pie | na)) & ((1 << n) - 1);
        while (bit != 0) {
            int p = bit & -bit;
            bit = bit & (bit - 1);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((1 << i) == p) sb.append("Q");
                else sb.append(".");
            }
            String s = sb.toString();
            list.add(s);
            solveNQueens(res, list, n, column | p, (pie | p) << 1, (na | p) >> 1);
            list.remove(s);
        }
    }

}